#pragma once
#include <iostream>
#include <vector>
#include<string>
using namespace std;

template<class K>
struct Hash
{
	size_t operator()(const K& key)
	{
		return key;
	}
};

namespace LinkHash
{
	template<class T>
	struct HashNode
	{
		T _data;
		HashNode<T>* next;
		
		HashNode(const T& data)
			:_data(data)
			,next(nullptr)
		{}
	};

	template<class K, class T, class KeyOfT, class HashFunc>
	struct HashTable;

	template<class K, class T, class Ref, class Ptr, class KeyOfT, class HashFunc>
	struct HashIterator
	{
		typedef HashNode<T> Node;
		typedef HashIterator<K, T, Ref, Ptr, KeyOfT, HashFunc> iterator;

		HashIterator(Node* node, HashTable<K, T, KeyOfT, HashFunc>* pht)
			:_node(node)
			,_pht(pht)
		{}

		Ref operator* ()
		{
			return _node->_data;
		}

		Ptr operator-> ()
		{
			return &_node->_data;
		}

		iterator& operator++()
		{
			if (_node->next)
				_node = _node->next;
			else
			{
				KeyOfT kot;
				HashFunc hf;
				size_t pos = hf(kot(_node->_data)) % _pht->_table.size() +1;
				while (pos < _pht->_table.size() && !_pht->_table[pos])
					pos++;
				if (pos == _pht->_table.size())
					_node = nullptr;
				else
					_node = _pht->_table[pos];
			}
			return *this;
		}

		bool operator==(const iterator& it) const
		{
			return(_node == it._node);
		}

		bool operator!=(const iterator& it) const
		{
			return(_node != it._node);
		}

		Node* _node;
		HashTable<K, T, KeyOfT, HashFunc>* _pht;
	};

	template<class K, class T, class KeyOfT, class HashFunc>
	class HashTable
	{
		typedef HashNode<T> Node;
		template<class K, class T, class Ref, class Ptr, class KeyOfT, class HashFunc>
		friend struct HashIterator;
	public:
		typedef HashIterator<K, T, T&, T*, KeyOfT, HashFunc> iterator;

		iterator begin()
		{
			size_t pos = 0;
			while (pos < _table.size())
			{
				if (_table[pos])
					return iterator(_table[pos], this);
				pos++;
			}
			return iterator(nullptr, this);
		}

		iterator end()
		{
			return iterator(nullptr, this);
		}

		Node* Find(const K& key)
		{
			if (_n == 0)
				return nullptr;
			KeyOfT kot;
			HashFunc hf;
			size_t pos = hf(key) % _table.size();
			Node* cur = _table[pos];
			while (cur)
			{
				if (kot(cur->_data) == key)
					return cur;
				cur = cur->next;
			}
			return nullptr;
		}

		bool Erase(const K& key)
		{
			if (_n == 0)
				return false;
			KeyOfT kot;
			HashFunc hf;
			size_t pos = hf(key) % _table.size();
			Node* prev = nullptr;
			Node* cur = _table[pos];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					if (prev)
						prev->next = cur->next;
					else
						_table[pos] = cur->next;
					free(cur);
					_n--;
					return true;
				}
				prev = cur;
				cur = cur->next;
			}
			return false;
		}

		bool Insert(const T& data)
		{
			KeyOfT kot;
			if(Find(kot(data)))
				return false;
			HashFunc hf;
			if (_n == _table.size())
			{
				size_t newSize = _table.size() ? _table.size()*2 : 10;
				vector<Node*> newTable(newSize, nullptr);
				for (size_t i = 0; i < _table.size(); i++)
				{
					Node* cur=_table[i];
					while (cur)
					{
						Node* next = cur->next;
						size_t pos = hf(kot(cur->_data)) % newSize;
						cur->next = newTable[pos];
						newTable[pos] = cur;
						cur = next;
					}
					_table[i] = nullptr;
				}
				_table.swap(newTable);
			}
			
			size_t pos = hf(kot(data)) % _table.size();
			Node* newnode = new Node(data);
			newnode->next= _table[pos];
			_table[pos] = newnode;
			_n++;
			return true;
		}
	private:
		vector<Node*> _table;
		size_t _n=0;
	};

}
